// https://www.lintcode.com/problem/trapping-rain-water/description

class Solution {
public:
    /**
     * @param heights: a list of integers
     * @return: a integer
     */
    //法一：
    // int trapRainWater(vector<int> &heights) {
    //     int maxHeight = 0;
    //     int maxIndex = 0;
    //     int sum = 0;
    //     for (int i = 0; i < heights.size(); ++i)
    //     {
    //         if (heights[i] > maxHeight) 
    //         {
    //             maxHeight = heights[i];
    //             maxIndex = i;
    //         }
    //     }
    //     maxHeight = 0;
    //     for (int i = 0; i < maxIndex; ++i)
    //     {
    //         if (heights[i] > maxHeight) maxHeight = heights[i];
    //         else sum += (maxHeight - heights[i]); 
    //     }
    //     maxHeight = 0;
    //     for (int i = heights.size() - 1; i > maxIndex; --i)
    //     {
    //         if (heights[i] > maxHeight) maxHeight = heights[i];
    //         else sum += (maxHeight - heights[i]);
    //     }
    //     return sum;
    // }
    
    // 法二：双指针
    int trapRainWater(vector<int> &heights) {
        int l = 0;
        int r = heights.size() - 1;
        int lMax = 0;
        int rMax = 0;
        int sum = 0;
        while (l <= r)
        {
            // if (heights[l] > lMax) lMax = heights[l++];
            // if (heights[r] > rMax) rMax = heights[r--];
            // else sum += () //注意不是同时灌，同时灌不能确定中间有没有更大的。
            if (lMax <= rMax)
            {
                if (heights[l] > lMax) lMax = heights[l];
                else sum += (lMax - heights[l]);
                l++;
            }
            else
            {
                if (heights[r] > rMax) rMax = heights[r];
                else sum += (rMax - heights[r]);
                r--;
            }
        }
        return sum;
    }
};

// update 2021.11.27
// https://leetcode-cn.com/problems/trapping-rain-water/submissions/
// 法一：dp
class Solution {
public:
    int trap(vector<int>& height) {
        int sum = 0;
        if (height.empty()) return 0;
        int n = height.size();
        vector<int> leftMax(n);
        vector<int> rightMax(n);
        leftMax[0] = height[0];
        rightMax[n - 1] = height[n - 1];
        for (int i = 1; i < height.size(); ++i) {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = max(rightMax[i + 1], height[i]);
        }
        for (int i = 0; i < height.size(); ++i) {
            sum += min(leftMax[i], rightMax[i]) - height[i];
        }
        return sum;
    }
};

// 法二：双指针
class Solution {
public:
    int trap(vector<int>& height) {
        int l = 0;
        int r = height.size() - 1;
        int lmax = 0;
        int rmax = 0;
        int sum = 0;
        while (l <= r) {
           if (lmax <= rmax) {
               if (height[l] > lmax) lmax = height[l];
               sum += lmax - height[l];
               l++;
           } else {
               if (height[r] > rmax) rmax = height[r];
               sum += rmax - height[r];
               r--;
           }
        }
        return sum;
    }
};

// https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode-solution-tuvc/
// 单调栈，单调递减，每次遇到比top高的，就和top前面的一起对比填坑。小坑填平，再填大坑。
class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> s;
        int sum = 0;
        for (int i = 0; i < height.size(); ++i) {
            while (!s.empty() && height[i] > height[s.top()]) {
                int top = s.top();
                s.pop();
                if (s.empty()) break;
                int left = s.top();
                int width = i - left - 1;
                int h = min(height[left], height[i]) - height[top];
                sum += h * width;
            }
            s.push(i);
        }
        return sum;
    }
};